package my.algo.graph;

import java.util.LinkedList;
import java.util.Arrays;

/**
 * 使用邻接表表示图
 */
public class LGraph {

	private final int nv;
	private int ne;
	private LinkedList<Integer>[] adj;

	private boolean[] marked;

	public LGraph(int nv) {
		this.nv = nv;
		this.ne = 0;
		adj = (LinkedList<Integer>[]) new LinkedList[nv];
		for (int i = 0; i < nv; i++) {
			adj[i] = new LinkedList<Integer>();
		}
		marked = new boolean[nv];
	}

	public LGraph addEdge(int v, int w) {
		adj[v].add(w);
		ne++;
		return this;
	}
	
	/**
	 * 深度优先遍历
	 */
	public void depthFirstSearch(int v) {
		marked[v] = true;
		for (Integer i : adj[v]) {
			if (marked[i]) {
				continue;
			}
			System.out.print(i + " ");
			depthFirstSearch(i);
		}
	}

	/**
	 * 广度优先遍历
	 */
	public void breadthFirstSearch(int v) {
		LinkedList<Integer> queue = new LinkedList<>();
		queue.addLast(v);
		marked[v] = true;
		while (!queue.isEmpty()) {
			int p = queue.removeFirst();
			System.out.print(p + " ");
			for (Integer i : adj[p]) {
				if (marked[i]) {
					continue;
				}
				marked[i] = true;
				queue.addLast(i);
			}
		}
	}

	/**
	 * 最短路径算法
	 */
	public void minDistance(int v) {
		int[] dist = new int[nv];
		int[] path = new int[nv];
		for (int i = 0; i < dist.length; i++) {
			dist[i] = -1;
			path[i] = -1;
		}
		dist[v] = 0;

		LinkedList<Integer> queue = new LinkedList<>();
		queue.addLast(v);
		while (!queue.isEmpty()) {
			int p = queue.removeFirst();
			for (Integer i : adj[p]) {
				if (dist[i] != -1) {
					continue;
				}
				dist[i] = dist[p] + 1;
				path[i] = p;
				queue.addLast(i);
			}
		}

		for (int i = 0; i < dist.length; i++) {
			System.out.print(i + ":" + dist[i] + " ");
		}
		System.out.println();
		System.out.println(Arrays.toString(path));
	}

	private void print() {
		for (int i = 0; i < adj.length; i++) {
			for (int j : adj[i]) {
				System.out.print(j);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		LGraph graph = new LGraph(6);
		graph.addEdge(0, 1).addEdge(0, 2).addEdge(0, 5);
		graph.addEdge(1, 0);
		graph.addEdge(2, 0).addEdge(2, 3).addEdge(2, 4);
		graph.addEdge(3, 2).addEdge(3, 4).addEdge(3, 5);
		graph.addEdge(4, 2).addEdge(4, 3);
		graph.addEdge(5, 0).addEdge(5, 3);
		graph.print();
		graph.depthFirstSearch(0);
		//graph.breadthFirstSearch(0);
		System.out.println();
		graph.minDistance(0);
		System.out.println();
	}
}
